`
https://leetcode.cn/problems/path-with-minimum-effort/
`

/**
 * @param {number[][]} heights
 * @return {number}
 */
var minimumEffortPath = function (heights) {
  const m = heights.length
  const n = heights[0].length
  const pq = new Heap((a, b) => a.phy - b.phy)
  pq.push(new State(0, 0, 0))
  // Infinity 表示还没走过，初始化为正无穷方便找到更小的体力消耗
  const distTo = Array.from({ length: m }, () => new Array(n).fill(Infinity))
  distTo[0][0] = 0
  const direc = [[1, 0], [-1, 0], [0, 1], [0, -1]]

  const isValid = (x, y) => {
    return x >= 0 && y >= 0 && x < m && y < n
  }

  while (!pq.isEmpty()) {
    // 拿到当前所在节点
    const curNode = pq.pop()
    const curX = curNode.x
    const curY = curNode.y
    const curPhy = curNode.phy

    // 到达终点，直接返回就是最小的体力消耗
    if (curX === m - 1 && curY === n - 1) {
      return curPhy
    }

    for (const [x, y] of direc) {
      const nextX = curX + x
      const nextY = curY + y
      if (!isValid(nextX, nextY)) continue
      // 计算出当前路径要进入下一个目标节点至少需要多少体力
      const nextPhy = Math.max(curPhy, Math.abs(heights[nextX][nextY] - heights[curX][curY]))
      // 新路径比旧路径更节省体力再进行更新，把新节点入队
      if (nextPhy < distTo[nextX][nextY]) {
        distTo[nextX][nextY] = nextPhy
        pq.push(new State(nextX, nextY, nextPhy))
      }
    }
  }
};

class State {
  constructor(x, y, phy) {
    this.x = x
    this.y = y
    this.phy = phy
  }
}